Adders are extremely common and indispensable operators not only in the arithmetic units of digital signal processing microprocessors and processors but likewise in all logic circuits.
However, adders often prove to be the critical operators of a digital processing system, in particular during certain implementations, both from the viewpoint of the speed of execution thereof and the viewpoint of the design and testability of same.
As a matter of fact, nowadays, the creation of algorithms of increasing complexity within computers makes the architecture of the operators increasingly difficult to implement and, in particular, compactness problems arise. A choice must therefore generally be made between complexity and speed of execution.
The technical problem of the computing speed with respect to binary number addition operations is a problem known to those skilled in the art, and several techniques have already been proposed for addressing it.
In a first standard technique, by cascading several 1-bit full adders, the binary adder, more commonly named a Ripple Carry Adder (RCA), enables the carry digit to be propagated from adder to adder.
The disadvantage of this first standard technique is the slowness of the computations that it implements. As a matter of fact, the computing time depends directly on the time required to propagate the carry digit from adder module to adder module. Thus, this method can only be chosen for addition operations which do not exceed a few bits.
Taking account of the fact that computation of the carry digits must be accelerated, a second known technique is a carry look-ahead computation carried out with a so-called Carry Look-Ahead Adder (CLA). Such an adder facilitates, in particular, computation of the carry digits by means of an outside circuit.
However, this type of standard adder has the disadvantage of providing a propagation time that is still too long, in particular for applications including complex algorithms and requiring fast computation.
In order to prevent propagation of the carry digits and to thereby improve the execution time of the computations, another conventionally used technique consists of an addition of binary numbers in redundant form, using an adder structure also known as a carry save adder. These standard adders use redundant expressions which enable additions to be performed in parallel, and therefore without propagating carry digits.
To illustrate, the American patent documents U.S. Pat. No. 6,578,063 B1 (IBM) and U.S. Pat. No. 6,567,835 B1 (INTRINSITY) propose two binary number adder architectures of the “carry save” type. These two architectures enable five binary numbers to be added and to furnish the result thereof in the form of a sum and a carry digit. The conventional method cited in these documents consists in using, in particular, a redundant representation of each of the added binary numbers.
However, the standard “carry save” layout described requires a significant number of logic gates and intermediate digital processing stages. Since the architecture and layout of the logic devices is not optimised, this method involves a still significant propagation time.
One known technique, as described in the international application WO2007122319 (TORNO), consists in making several estimates of bit values of the sum of two binary numbers, by means of a “U/R” type redundant binary representation of the intermediate computation results, and in successively correcting these estimates using a correction signal. The number of logic gates and intermediate digital processing stages of this type of adder is thereby reduced.
This method, which is based on a “U/R” type representation, is today unfortunately applicable only for adding two binary numbers. Accordingly, if it is desired to add more than two binary numbers, this method must be applied to two numbers, and then (as many times as necessary) to the result of a preceding addition and a new binary number. This solution is not optimal.